import java.util.ArrayList;
import java.util.List;

public class Leetcode {
}

//leetcode:912:排序数组
//归并排序
class Solution1 {
    int[] tmp;
    public int[] sortArray(int[] nums) {
        tmp = new int[nums.length];
        mergesort(nums,0,nums.length-1);
        return nums;
    }

    public void mergesort(int[] nums,int start,int end){
        if(start >= end){
            return;
        }

        int mid =start + (end - start) / 2;
        mergesort(nums,start,mid);
        mergesort(nums,mid+1,end);

        int left = start,right = mid+1,k = 0;
        while(left <= mid && right <= end){
            tmp[k++] = nums[left] <= nums[right] ? nums[left++] : nums[right++];
        }
        while(left <= mid){
            tmp[k++] = nums[left++];
        }
        while(right <= end){
            tmp[k++] = nums[right++];
        }

        for(int i = start;i <= end;i++){
            nums[i] = tmp[i-start];
        }
    }
}

//leetcode:LCR 170.交易交易逆序对的总数
//归并排序
class Solution2 {
    int[] tmp;
    public int reversePairs(int[] record) {
        int n = record.length;
        tmp = new int[n];
        return mergesort(record,0,n-1);
    }

    public int mergesort(int[] nums,int left,int right){
        if(left >= right){
            return 0;
        }
        int ret = 0;
        int mid = left + (right - left) / 2;


        //将数组分成两部分，得到这两部分所以的逆序对
        ret += mergesort(nums,left,mid);
        ret += mergesort(nums,mid+1,right);

        //在合并两个数组的同时，计算左边元元素大于右边元素的组队个数
        int cur1 = left, cur2 = mid+1,k = 0;
        //在合并之前这两部个部分都是升序的
        while(cur1 <= mid && cur2 <= right){
            //如果左边的元素要小于等于右边的元素，就代表我们不能组成逆序对
            if(nums[cur1] <= nums[cur2]){
                tmp[k++] = nums[cur1++];//让cur1往后走，继续找左边比右边大的元素，同时排序数组
            }else{//如果我们的左边元素比右边元素大，就代表我们左边此时元素的后边元素都比此时的右边这个元素大，都能够组成一个逆序对
                ret += mid - cur1 + 1;//此时左边从这个元素开始到结束都可以组成逆序对，且逆序对的个数为左边从这个元素开始到结束的长度
                tmp[k++] = nums[cur2++];//让cur2往后走，判断下一个元素是否还比左边元素小，同时排序数组
            }
        }

        //处理边界问题，如果一边走到头了就将另一边的元素放到数组中
        while(cur1 <= mid){
            tmp[k++] = nums[cur1++];
        }
        while(cur2 <= right){
            tmp[k++] = nums[cur2++];
        }
        //根据临时数组，更新元素数组的值
        for(int i = left;i <= right;i++){
            nums[i] = tmp[i-left];
        }
        return ret;//放回逆序对的个数
    }
}

//leetcode:315:计算右侧小于当前元素的个数
class Solution {
    int[] ret;
    int[] index;//存储元素的位置
    int[] tmpIndex;//存储排序后元素的位置
    int[] tmpNums;//创建临时数组存储排序后的元素
    public List<Integer> countSmaller(int[] nums) {
        int n = nums.length;
        ret = new int[n];
        index = new int[n];
        tmpIndex = new int[n];
        tmpNums = new int[n];
        //初始化
        for(int i = 0;i < n;i++){
            index[i] = i;
        }
        mergesort(nums,0,n-1);
        ArrayList<Integer> list = new ArrayList<>();
        for(int x : ret){
            list.add(x);
        }
        return list;
    }

    public void mergesort(int[] nums,int left,int right){
        if(left >= right){
            return;
        }

        int mid = left + (right - left) / 2;
        mergesort(nums,left,mid);
        mergesort(nums,mid+1,right);

        //合并数组
        int cur1 = left,cur2 = mid+1,k = 0;
        while(cur1 <= mid && cur2 <= right){
            if(nums[cur1] <= nums[cur2]){
                tmpNums[k] = nums[cur2];
                tmpIndex[k++] = index[cur2++];
            }else{
                ret[index[cur1]] += right - cur2 +1;
                tmpNums[k] = nums[cur1];
                tmpIndex[k++] = index[cur1++];
            }
        }

        while(cur1 <= mid){
            tmpNums[k] = nums[cur1];
            tmpIndex[k++] = index[cur1++];
        }
        while(cur2 <= right){
            tmpNums[k] = nums[cur2];
            tmpIndex[k++] = index[cur2++];
        }
        for(int i = left ;i <= right;i++){
            nums[i] = tmpNums[i-left];
            index[i] = tmpIndex[i-left];
        }
    }
}

//leetcode:193:翻转对
class Solution3 {
    int[] tmp;
    public int reversePairs(int[] nums) {
        int n = nums.length;
        tmp = new int[n];
        return mergesort(nums,0,n-1);
    }
    public int mergesort(int[] nums,int left,int right){
        if(left >= right) return 0;

        int ret = 0;
        int mid = left + (right - left) / 2;
        ret += mergesort(nums,left,mid);
        ret += mergesort(nums,mid+1,right);

        //先计算出每一部分的翻转对的个数
        int cur1 = left,cur2 = mid+1;
        while(cur2 <= right){
            while(cur1 <= mid && (long)nums[cur1] <=(long)2*nums[cur2]){//如果cur1位置的元素不大于2倍cur2位置的元素，就继续往后找
                cur1++;
            }
            //如果走完了左边的就结束
            if(cur1 > mid) break;
            ret += mid - cur1 + 1;//如果找了cur1位置的元素大于2倍cur2位置的元素，由于是升序排列就代表此时左边这个元素的后面所有元素都大于右边此时的元素
            cur2++;               //此时左边这个元素到最后的长度就是我们的翻转对个数，然后让cur2往后走判断下一个元素判断下一个元素是否还比左边元素小。

        }
        cur1 = left;cur2= mid+1;
        int k = 0;
       //最后我们再排序这一部分我们的数组
        while(cur1 <= mid && cur2 <= right){
            if(nums[cur1] <= nums[cur2]){
                tmp[k++] = nums[cur1++];
            }else{
                tmp[k++] = nums[cur2++];
            }
        }
        while(cur1 <= mid){
            tmp[k++] = nums[cur1++];
        }
        while(cur2 <= right){
            tmp[k++] = nums[cur2++];
        }
        for(int i = left;i <= right;i++){
            nums[i] = tmp[i-left];
        }
        return ret;
    }
}